package demo3;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class GraphByNode {
    static class Node {
        public int src;     // 起始位置
        public int dest;    // 目标位置
        public int weight;  // 权重
        public Node next;

        public Node (int src, int dext, int weight) {
            this.src = src;
            this.dest = dext;
            this.weight = weight;
        }
    }

    public char[] arrayV;
    public ArrayList<Node> edglist; // 存储边
    public boolean isDirect;

    public GraphByNode (int size, boolean isDirect) {
        this.arrayV = new char[size];
        edglist = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            edglist.add(null);
        }
        this.isDirect = isDirect;
    }

    /**
     * 初始化顶点数组
     * @param array
     */
    public void initArrayV(char[] array) {
        for (int i = 0; i < array.length; i++) {
            arrayV[i] = array[i];
        }
    }

    /**
     * 添加边
     * @param srcV
     * @param destV
     * @param weight
     */
    public void addEdge (char srcV, char destV, int weight) {
        int srcIndex = getIndexOfV(srcV);
        int destIndex = getIndexOfV(destV);
        addEdgeChild(srcIndex, destIndex, weight);
        //无向图 需要添加两条边
        if (!isDirect) {
            addEdgeChild(destIndex, srcIndex, weight);
        }
    }

    private void addEdgeChild (int srcIndex, int destIndex, int weight) {
        Node cur = edglist.get(srcIndex);
        while (cur != null) {
            if (cur.dest == destIndex) return;
            cur = cur.next;
        }
        //之前没有存储过这条边  头插法
        Node node = new Node(srcIndex, destIndex, weight);
        node.next = edglist.get(srcIndex);
        edglist.set(srcIndex, node);
    }

    /**
     * 获取顶点V的下标
     * @param v
     * @return
     */
    private int getIndexOfV(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if (arrayV[i] == v) return i;
        }
        return -1;
    }

    public void printGraph () {
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print(arrayV[i]);
            Node cur = edglist.get(i);
            while (cur != null) {
                System.out.print("->" + arrayV[cur.dest]);
                cur = cur.next;
            }
            System.out.println();
        }
    }

    /**
     * 获取顶点的度
     * @param v
     * @return
     */
    public int getDevOfV (char v) {
        int count = 0;
        int srcIndex = getIndexOfV(v);
        Node cur = edglist.get(srcIndex);

        while (cur != null) {
            count++;
            cur = cur.next;
        }

        // 只计算了出度
        if (isDirect) {
            int destIndex = srcIndex;
            for (int i = 0; i < arrayV.length; i++) {
                if (i == destIndex) {
                    continue;
                }else {
                    Node pcur = edglist.get(i);
                    while (pcur != null) {
                        if (pcur.dest == destIndex) {
                            count++;
                        }
                        pcur = pcur.next;
                    }
                }
            }
        }
        return count;
    }



    public static void main(String[] args) {
        char[] chars = new char[] {'A', 'B', 'C', 'D'};
        GraphByNode graph = new GraphByNode(chars.length, false);
        graph.initArrayV(chars);

        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);
        graph.printGraph();
        System.out.println("getDevOfV::" + graph.getDevOfV('A'));
    }
}
